In a number of situations a given parameter y, which is a continuous linear function of a first parameter x, must be represented by choosing discrete locations in a two dimensional grid of possible x and y values. Each point of the grid is located at the intersection of the x and y values associated with that grid point. The grid points thus formed are often referred to as "picture elements" or "pixels". In order to most accurately map a continuous linear function onto this type of two dimensional grid, the pixels chosen to represent the function must be those which are located closest to the true x and y values for the function.
A common example of this type of mapping problem is representing a continuous line on a two dimensional raster grid. In order to do so, the x and y coordinates of the pixels located closest to the true line must be determined, where x and y have integer values. The algorithms used to determine the pixel coordinates are often referred to as scan-conversion algorithms. Typically, the pixel coordinates determined by the algorithm are stored in memory devices at addresses which correspond to the raster grid locations. Conventional raster scan display techniques may then be utilized to display the resulting line by scanning the memory and by illuminating the pixel locations stored therein.
In a typical raster display, the scan-conversion algorithm employed will be invoked quite frequently, possibly as often as hundreds or even thousands of repetitions each time an image is created or modified on the display. Hence, in addition to satisfactorily determining the pixel locations, the algorithm used must also execute as rapidly as possible. Speed versus image quality is often the trade off used in selecting the scan-conversion algorithm. In order to provide the fastest execution for a given algorithm, incremental methods are utilized which minimize the number of calculations, and especially the number of multiplications and divisions, performed during each iteration of the algorithm.
Most conventional raster displays rasterize a continuous line one pixel at a time, with each pixel being generated in sequence. Perhaps the most widely used algorithm for doing so is known as Bresenham's line algorithm. An explanation of this algorithm may be found in many computer graphics text books. For example, a description of the algorithm, as well as its derivation, are presented at pages 431-436 of Fundamentals of Interactive Computer Graphics by J. D. Foley and A. Van Dam, Addison-Wesley Publishing Company, Inc. (1982), which is incorporated herein by reference. Briefly described, Bresenham's algorithm determines a running error term as well as correction terms to be applied to the running error term as various pixel locations are chosen to represent the true line. The initial error term and each of the correction terms is determined from the total x and y displacements traversed by the line. For each particular pixel, the error term associated with that pixel reflects the amount that the pixel deviates from the true line location. Thus, the error terms for the various pixels may be utilized to determine which pixels are closest to the line. As pixel locations are sequentially chosen and the algorithm is reiterated to choose subsequent pixel locations, the appropriate correction term is added to the running error term in order to account for the change in the error term produced by choosing the previous pixel location. This process is continued until the end of the line is reached and the last pixel location is chosen.
Bresenham's algorithm uses only integer arithmetic, and it lends itself to incremental techniques for performing repetitive calculations of the algorithm. Moreover, the calculations themselves involve only addition, subtraction, and left shifts of binary data. Time-consuming multiplications and divisions are avoided. Consequently, Bresenham's algorithm provides an efficient means for rasterizing a line. However, the algorithm generates only one pixel location in a given machine cycle of the generation hardware. To improve the performance of raster display systems, faster scan-conversion techniques are needed. Furthermore, the pixel locations being generated must be capable of being stored in the raster display's frame buffer memory in such a manner that memory access conflicts are avoided or resolved.
Accordingly, it is an object of the present invention to provide a technique for generating more than one pixel location for a rasterized line in a given machine cycle.
It is a further object of the present invention to provide a method for generating multiple pixel locations in such a manner that memory access conflicts can be resolved while the pixels are being generated, without requiring additional machine cycles for accomplishing the resolution.
It is another object of this invention to provide a pixel generation system in which the calculations involved in determining the pixel locations may be executed quickly using commercially available hardware.
It is also an object of the present invention to provide a pixel generation system which can be adapted to generate a predetermined number of pixels during a given machine cycle.